#include <iostream>
#include <vector>
#include <format>
using namespace std;
// 阶乘
int fact(int n) {
  if (n == 1) return 1;
  return n * fact(n - 1);
}

// 斐波那契数列
long long fib(int n) {
  if (n <= 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

// 带记忆化的斐波那契数列
long long fib(auto &saved, int n) {
  if (n <= 2) return 1;
  long long &memo = saved[n];
  if (memo != -1) return memo;
  return memo = fib(saved, n - 1) + fib(saved, n - 2);
}

// 汉诺塔
void hanoi(int n, char F, char A, char T) {
  if (n == 1) {
    cout << format("move {} from {} to {}", n, F, T) << endl;
    return;
  }
  hanoi(n - 1, F, T, A);
  cout << format("move {} from {} to {}", n, F, T) << endl;
  hanoi(n - 1, A, F, T);
}

int main() {
  cout << fact(5) << endl;
  // cout << fib(60) << endl; // very slow
  vector<long long> saved(61, -1);
  cout << fib(saved, 60) << endl;
  hanoi(3, 'A', 'B', 'C');
}